#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType val;
}BTNode;
void TreeDestroy(BTNode*root)
{
	if (root == NULL)
	{
		return;
	}
	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}
BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("BuyBTNode->malloc failed");
		exit(-1);
	}
	newnode->val = x;
	newnode->right = NULL;
	newnode->left = NULL;
	return newnode;
}
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	BTNode* ret = NULL;
	ret = TreeFind(root->left, x);
	if (ret != NULL)
		return ret;
	ret = TreeFind(root->right, x);
	if (ret != NULL)
		return ret;
	return ret;
	//if (TreeFind(root->left, x) != NULL)
	//	return TreeFind(root->left, x);
	//if (TreeFind(root->right, x) != NULL)
	//	return TreeFind(root->right, x);
	//return NULL;
}
void Test1()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	//PrevOrder(node1);
	//TreeDestroy(node1);
	//node1 = NULL;
	printf("%p=node5\n", node5);
	printf("%p=ret\n", TreeFind(node1, 5));
}
struct TreeNode
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
	if (p != NULL && q != NULL)
		return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
	if (p == NULL && q == NULL)
		return true;
	return false;
}
int preorderSize(struct TreeNode* root)
{
	if (root == NULL)
		return 0;
	return preorderSize(root->left) + preorderSize(root->right) + 1;
	//return root == NULL ? 0 : preorderSize(root->left) + preorderSize(root->right) + 1;
}
void preorder(struct TreeNode* root, int* a, int* i)
{
	if (root == NULL)
		return;
	a[*i] = root->val;
	(*i)++;
	preorder(root->left, a, i);
	preorder(root->right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
	int n = preorderSize(root);
	int* a = (int*)malloc(sizeof(int) * n);
	int j = 0;
	preorder(root, a, &j);
	*returnSize = n;
	return a;
}
bool isSameTree0(struct TreeNode* p, struct TreeNode* q)
{
	if (p == NULL && q == NULL)
		return true;
	if (p != NULL && q != NULL)
		return p->val == q->val && isSameTree0(p->left, q->left) && isSameTree0(p->right, q->right);
	return false;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{
	if (subRoot == NULL)
		return true;
	if (root == NULL)
		return false;
	return isSameTree0(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
int main()
{
	//Test1();
	return 0;
}


